The complexity of some complementation problems
Identifieur interne : 00A825 ( Main/Exploration ); précédent : 00A824; suivant : 00A826The complexity of some complementation problems
Auteurs : David A. Plaisted [États-Unis] ; Gregory Kucherov [États-Unis, France]Source :
- Information Processing Letters [ 0020-0190 ] ; 1999.
Descripteurs français
- Pascal (Inist)
- mix :
English descriptors
- KwdEn :
- Teeft :
- Atomic representations, Chapel hill, Complement problem, Complement problems, Complement representation, Complement representation problem, Complementation problem, Complexity questions, Computational complexity, Computer science, Constant size, Constant symbols, Disjoint, Distinct terms, Elementary substitution, Elsevier science, Empty complement, Exponential, Exponential size, Function symbols, Ground reducibility, Ground term, Ground terms, Herbrand models, Hierarchical, Hierarchical sets, Ieee symposium, International workshop, Kucherov, Kucherov information processing letters, Lassez, Lecture notes, Linear terms, Logic programming, Maximal depth, Model building, Nite, Nite complement representation, Normal forms, Other hand, Other term, Plaisted, Position form, Quadratic, Smallest position, Springer, Such terms, Symbol size, Worst case.
Abstract
Abstract: We study the computational complexity of the problem of computing a complement representation for a set of terms. Depending on the class of sets considered, some sets are shown to have an exponential complement representation in the worst case, and some are shown to have a polynomial one. The complexity of deciding if a set has an empty complement is also studied.
Url:
DOI: 10.1016/S0020-0190(99)00102-7
Affiliations:
- France, États-Unis
- Caroline du Nord, Grand Est, Lorraine (région)
- Chapel Hill (Caroline du Nord), Villers-lès-Nancy
- Université de Caroline du Nord à Chapel Hill
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002289
- to stream Istex, to step Curation: 002258
- to stream Istex, to step Checkpoint: 002209
- to stream Main, to step Merge: 00AE76
- to stream Hal, to step Corpus: 004C32
- to stream Hal, to step Curation: 004C32
- to stream Hal, to step Checkpoint: 006542
- to stream Main, to step Merge: 00B326
- to stream PascalFrancis, to step Corpus: 000A86
- to stream PascalFrancis, to step Curation: 000D84
- to stream PascalFrancis, to step Checkpoint: 000A65
- to stream Main, to step Merge: 00B153
- to stream Main, to step Curation: 00A825
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>The complexity of some complementation problems</title><author><name sortKey="Plaisted, David A" sort="Plaisted, David A" uniqKey="Plaisted D" first="David A." last="Plaisted">David A. Plaisted</name></author><author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:953B751135141EFA971202B8DADFF3D9105C6C90</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1016/S0020-0190(99)00102-7</idno><idno type="url">https://api.istex.fr/ark:/67375/6H6-W72M07NQ-S/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002289</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002289</idno><idno type="wicri:Area/Istex/Curation">002258</idno><idno type="wicri:Area/Istex/Checkpoint">002209</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002209</idno><idno type="wicri:doubleKey">0020-0190:1999:Plaisted D:the:complexity:of</idno><idno type="wicri:Area/Main/Merge">00AE76</idno><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00098851</idno><idno type="url">https://hal.inria.fr/inria-00098851</idno><idno type="wicri:Area/Hal/Corpus">004C32</idno><idno type="wicri:Area/Hal/Curation">004C32</idno><idno type="wicri:Area/Hal/Checkpoint">006542</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">006542</idno><idno type="wicri:doubleKey">0020-0190:1999:Plaisted D:the:complexity:of</idno><idno type="wicri:Area/Main/Merge">00B326</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:99-0529151</idno><idno type="wicri:Area/PascalFrancis/Corpus">000A86</idno><idno type="wicri:Area/PascalFrancis/Curation">000D84</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000A65</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000A65</idno><idno type="wicri:doubleKey">0020-0190:1999:Plaisted D:the:complexity:of</idno><idno type="wicri:Area/Main/Merge">00B153</idno><idno type="wicri:Area/Main/Curation">00A825</idno><idno type="wicri:Area/Main/Exploration">00A825</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">The complexity of some complementation problems</title><author><name sortKey="Plaisted, David A" sort="Plaisted, David A" uniqKey="Plaisted D" first="David A." last="Plaisted">David A. Plaisted</name><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation><affiliation wicri:level="4"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175</wicri:regionArea><placeName><region type="state">Caroline du Nord</region><settlement type="city">Chapel Hill (Caroline du Nord)</settlement></placeName><orgName type="university">Université de Caroline du Nord à Chapel Hill</orgName></affiliation></author><author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Villers-lès-Nancy</settlement></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">Information Processing Letters</title><title level="j" type="abbrev">IPL</title><idno type="ISSN">0020-0190</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999">1999</date><biblScope unit="volume">71</biblScope><biblScope unit="issue">3–4</biblScope><biblScope unit="page" from="159">159</biblScope><biblScope unit="page" to="165">165</biblScope></imprint><idno type="ISSN">0020-0190</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0020-0190</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Complement representation</term><term>Complementation</term><term>Complementation problem</term><term>Computational complexity</term><term>Ground instance</term><term>Ground term</term><term>Learning</term><term>Representation</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Apprentissage</term><term>Complexité calcul</term><term>Complémentation</term><term>Instance de base</term><term>Problème complémentation</term><term>Représentation</term><term>Représentation complément</term><term>Terme de base</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Atomic representations</term><term>Chapel hill</term><term>Complement problem</term><term>Complement problems</term><term>Complement representation</term><term>Complement representation problem</term><term>Complementation problem</term><term>Complexity questions</term><term>Computational complexity</term><term>Computer science</term><term>Constant size</term><term>Constant symbols</term><term>Disjoint</term><term>Distinct terms</term><term>Elementary substitution</term><term>Elsevier science</term><term>Empty complement</term><term>Exponential</term><term>Exponential size</term><term>Function symbols</term><term>Ground reducibility</term><term>Ground term</term><term>Ground terms</term><term>Herbrand models</term><term>Hierarchical</term><term>Hierarchical sets</term><term>Ieee symposium</term><term>International workshop</term><term>Kucherov</term><term>Kucherov information processing letters</term><term>Lassez</term><term>Lecture notes</term><term>Linear terms</term><term>Logic programming</term><term>Maximal depth</term><term>Model building</term><term>Nite</term><term>Nite complement representation</term><term>Normal forms</term><term>Other hand</term><term>Other term</term><term>Plaisted</term><term>Position form</term><term>Quadratic</term><term>Smallest position</term><term>Springer</term><term>Such terms</term><term>Symbol size</term><term>Worst case</term></keywords><keywords scheme="mix" xml:lang="fr"><term>complement representation</term><term>complexité</term><term>computational complexity</term><term>ground instance</term><term>ground term</term><term>représentation du complément</term><term>term</term><term>terme</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We study the computational complexity of the problem of computing a complement representation for a set of terms. Depending on the class of sets considered, some sets are shown to have an exponential complement representation in the worst case, and some are shown to have a polynomial one. The complexity of deciding if a set has an empty complement is also studied.</div></front></TEI><affiliations><list><country><li>France</li><li>États-Unis</li></country><region><li>Caroline du Nord</li><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Chapel Hill (Caroline du Nord)</li><li>Villers-lès-Nancy</li></settlement><orgName><li>Université de Caroline du Nord à Chapel Hill</li></orgName></list><tree><country name="États-Unis"><noRegion><name sortKey="Plaisted, David A" sort="Plaisted, David A" uniqKey="Plaisted D" first="David A." last="Plaisted">David A. Plaisted</name></noRegion><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name><name sortKey="Plaisted, David A" sort="Plaisted, David A" uniqKey="Plaisted D" first="David A." last="Plaisted">David A. Plaisted</name></country><country name="France"><region name="Grand Est"><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00A825 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00A825 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:953B751135141EFA971202B8DADFF3D9105C6C90
|texte= The complexity of some complementation problems
}}
| This area was generated with Dilib version V0.6.33. |  |